In image processing, it is common to perform a thinning process on a digital image. Thinning, or “skeletonization”, thins an input image into output branches of single pixel thickness. A thinning output should attempt to retain the connectedness and structure of the input image. Thinning is useful for identifying key pixels in fields such as medical imaging, fingerprinting technology, character recognition, airport security, logic/electrical circuit analysis, and soil and metallurgy crack analysis.
Some thinning procedures operate by eroding outer contours of the input image. There are also a number of iterative procedures which process pixels sequentially. There also exist procedures based on partitioning the input image prior to thinning. Using one of these procedures, it is ordinarily possible to generate a thinned output image.
However, the above thinning procedures have significant disadvantages. For example, procedures which perform thinning by eroding outer contours can result in a loss of critical patterns and structures. Iterative procedures may get closer to producing the required output, but tend to be very slow and computationally expensive, and thus are infeasible for many operations. Partitioning procedures require significant pre-processing before the thinning process is applied, and may also require significant post-processing to merge the partitions back together.